# encoding:utf-8

import sys
import copy

# 初始化文件的结构
# 第一行：矩阵长/宽
# 后续：已经摆放的位置，每一行一个位置，格式如[0,1]，以0为计数起点
init_file = open('in\\init.txt', mode='r', encoding='utf-8')
line = init_file.readline().lstrip()
matrix_len = int(line)
# 读取起始位置
init_pos = []
line = init_file.readline().lstrip()
while line:
    init_pos.append(eval(line))
    line = init_file.readline().lstrip()
init_file.close()

# 生成矩阵
map_list = [[0 for c in range(matrix_len)] for r in range(matrix_len)]

# 初始化
for i in init_pos:
    map_list[i[0]][i[1]] = 1


def print_matrix(t):
    # 打印二维数组
    for i in t:
        print(i)
    print('')


def check(t):
    # 检查是否全部摆满
    s = 0
    for i in t:
        for j in i:
            s += j
    if s == matrix_len:
        return True
    else:
        return False


# 求解核心
def find_next(r, mt):
    global su
    p0 = True  # 没有预设值
    for c1 in range(matrix_len):  # 检查——
        if mt[r][c1] == 1:
            p0 = False
            if r == matrix_len - 1:
                su += 1
                print('第 {} 种解法：'.format(su))
                print_matrix(mt)
                sys.exit(0)
            else:
                find_next(r + 1, mt)
            break
    if p0:
        for c in range(matrix_len):  # 对每个位置进行检查
            p = True  # 位置可用
            if p:
                for r1 in range(matrix_len):  # 检查|
                    if mt[r1][c] == 1:
                        p = False
                        break
            if p:
                for k in range(1, matrix_len - r):  # 检查/
                    if c - k >= 0 and mt[r + k][c - k] == 1:
                        p = False
                        break
            if p:
                for k in range(1, r + 1):  # 检查/
                    if c + k < matrix_len and mt[r - k][c + k] == 1:
                        p = False
                        break
            if p:
                for k in range(1, matrix_len - r):  # 检查\
                    if c + k < matrix_len and mt[r + k][c + k] == 1:
                        p = False
                        break
            if p:
                for k in range(1, r + 1):  # 检查\
                    if c - k >= 0 and mt[r - k][c - k] == 1:
                        p = False
                        break
            if p:  # 位置可用
                mt_n = copy.deepcopy(mt)
                mt_n[r][c] = 1
                if r == matrix_len - 1:
                    su += 1
                    print('第 {} 种解法：'.format(su))
                    print_matrix(mt_n)
                else:
                    find_next(r + 1, mt_n)


su = 0

print('初始 {0} × {0} 矩阵：'.format(matrix_len))
print_matrix(map_list)

find_next(0, map_list)
print('运行结束')
